#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020-08-05 9:27 上午
# @Author  : yangdy
# @File    : 2020-08-05.337.打家劫舍III
# @Software: PyCharmCE
from my_methods import *


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def rob(self, root: TreeNode) -> int:
        ans = 0
        if not root:
            return 0
        self.rob(root.left)
        self.rob(root.right)
        root.f = (root.left.g if root.left else 0) + (root.right.g if root.right else 0) + root.val
        root.g = (max(root.left.g, root.left.f) if root.left else 0) + \
                 (max(root.right.g, root.right.f) if root.right else 0)
        ans = max(root.f, root.g)
        return ans


def mk_tree(data):
    root = None
    if not data:
        return root
    root = TreeNode(data[0])
    i = 1
    que = [root]
    while que and i < len(data):
        new_que = []
        for x in que:
            left = TreeNode(data[i]) if data[i] else None
            i += 1
            x.left = left
            new_que.append(left)
            if i < len(data):
                right = TreeNode(data[i]) if data[i] else None
                i += 1
                x.right = right
                new_que.append(right)
        que = new_que

    return root


def display(root):
    print('----')

    def _display(rt, dep=0):
        if not rt:
            return
        _display(rt.right, dep+1)
        print(' '*dep, rt.val)
        _display(rt.left, dep+1)
    _display(root)
    print('----')


def display2(root):
    print('----')

    def _display(rt, dep=0):
        if not rt:
            return
        _display(rt.right, dep+1)
        print(' '*dep, rt.val, rt.g, rt.f)
        _display(rt.left, dep+1)
    _display(root)
    print('----')


questions = [
    ([3, 2, 3, None, 3, None, 1],),
    ([3, 4, 5, 1, 3, None, 1],),
]

rt1 = mk_tree(questions[0][0])
display(rt1)
Solution().rob(rt1)
display2(rt1)

work(questions, lambda q: Solution().rob(mk_tree(q[0])))

